package com.sheng.leetcode.year2023.month02.day17;

import org.junit.Test;

/**
 * @author by ls
 * @date 2023/2/17
 * <p>
 * 1139. 最大的以 1 为边界的正方形<p>
 * <p>
 * 给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成的最大 正方形 子网格，并返回该子网格中的元素数量。如果不存在，则返回 0。<p>
 * <p>
 * 示例 1：<p>
 * 输入：grid = [[1,1,1],[1,0,1],[1,1,1]]<p>
 * 输出：9<p>
 * <p>
 * 示例 2：<p>
 * 输入：grid = [[1,1,0,0]]<p>
 * 输出：1<p>
 * <p>
 * 提示：<p>
 * 1 <= grid.length <= 100<p>
 * 1 <= grid[0].length <= 100<p>
 * grid[i][j] 为 0 或 1<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/largest-1-bordered-square">1139. 最大的以 1 为边界的正方形</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1139 {

    @Test
    public void test01() {
        int[][] grid = {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
//        int[][] grid = {{1, 1, 0, 0}};
        System.out.println(new Solution().largest1BorderedSquare(grid));
    }
}

class Solution {
    public int largest1BorderedSquare(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        // 获取每个位置向下和向右的连续 1 的个数，记为 down[i][j] 和 right[i][j]
        int[][] down = new int[m][n];
        int[][] right = new int[m][n];
        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                if (grid[i][j] == 1) {
                    down[i][j] = i + 1 < m ? down[i + 1][j] + 1 : 1;
                    right[i][j] = j + 1 < n ? right[i][j + 1] + 1 : 1;
                }
            }
        }
        // 枚举正方形的边长 k，从最大的边长开始枚举，然后枚举正方形的左上角位置 (i, j)，如果满足条件，然后 k^2
        for (int k = Math.min(m, n); k > 0; --k) {
            for (int i = 0; i <= m - k; ++i) {
                for (int j = 0; j <= n - k; ++j) {
                    if (down[i][j] >= k && right[i][j] >= k && right[i + k - 1][j] >= k
                            && down[i][j + k - 1] >= k) {
                        return k * k;
                    }
                }
            }
        }
        return 0;
    }
}
